

// FIXME: >! is considered as an entire token

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Stack;

public class Parser {
	// //////////////////////////
	// BEGIN PHASE 1 VARIABLES //
	// //////////////////////////
	char asciiTrans;
	int intTrans;

	// ASCII starts at 32
	final int ESCAPE_SPACE = 127;
	final int ESCAPE_BACK_SLASH = 128;
	final int ESCAPE_ASTERISK = 129;
	final int ESCAPE_PLUS = 130;
	final int ESCAPE_QUESTION = 131;
	final int ESCAPE_OR = 132;
	final int ESCAPE_LEFT_BRACKET = 133;
	final int ESCAPE_RIGHT_BRACKET = 134;
	final int ESCAPE_LEFT_PAREN = 135;
	final int ESCAPE_RIGHT_PAREN = 136;
	final int ESCAPE_PERIOD = 137;
	final int ESCAPE_SINGLE_QUOTE = 138;
	final int ESCAPE_DOUBLE_QUOTE = 139;
	final int ESCAPE_UP_ARROW = 140;
	final int ESCAPE_MINUS = 141;
	final int EPSILON = 142;
	final int IN = 143;

	boolean notFlag, clsFlag, reFlag, orFlag, charFlag, idFlag;
	boolean excludeFlag, includeFlag; // determines whether we are going to do a
										// normal include [] or an exclude [^]
	boolean excludeSet; // if true, we are on the excluding set of [^] if false
						// then we are on the set to exclude from [] or
						// charClass
	boolean insideBracket;
	int pos; // position in the regex string
	int currState;
	int startState; // first state in a subexpression
	int endState; // last state in a subexpression
	int lastState; // highest number state achieved
	int finalState; // last in the NFA
	int nextAsciiValue;
	String lexSpec; // regex string to be examined
	private boolean validRegex; // states whether is regex string given has
								// valid syntax
	Stack<Integer> parenStack; // keeps track of nested parentheses
	HashSet<Integer> set; // temp set
	HashSet<Integer> finishingStates;
	HashSet<Integer> charClassValues;
	HashSet<Integer> includeValues;
	HashSet<Integer> excludeValues;
	HashSet<CharClass> characterClasses;
	HashSet<IdClass> idClasses;
	CharClass newestCharClass;
	IdClass newestId;
	// ////////////////////////
	// END PHASE 1 VARIABLES //
	// ////////////////////////
	int listPos;
	Token token;
	ArrayList<Token> list;
	ScannerGenerator generator;
	private Node head;
	private Node current;

	public Parser(String filename) {
		notFlag = false;
		clsFlag = false;
		reFlag = false;
		orFlag = false;
		charFlag = true;
		idFlag = false;
		excludeFlag = false;
		includeFlag = false;
		excludeSet = false;
		insideBracket = false;
		listPos = 0;
		pos = 0;
		currState = 1;
		lastState = 1;
		startState = 0;
		endState = 0;
		nextAsciiValue = 165;
		validRegex = true;
		characterClasses = new HashSet<CharClass>();
		idClasses = new HashSet<IdClass>();
		parenStack = new Stack<Integer>();
		charClassValues = new HashSet<Integer>();

		generator = new ScannerGenerator();
		list = generator.generateList(filename);
		head = new Node("<MiniRE-program>", "MiniREprogram", null, new ArrayList<Node>());
		MiniREprogram();
	}

	public Node getTreeHead() {
		return head;
	}

	/****************************************************************
	 * PHASE TWO RULES !!! PHASE TWO RULES !!! PHASE TWO RULES !!! * PHASE TWO
	 * RULES !!! PHASE TWO RULES !!! PHASE TWO RULES !!! * PHASE TWO RULES !!!
	 * PHASE TWO RULES !!! PHASE TWO RULES !!! * PHASE TWO RULES !!! PHASE TWO
	 * RULES !!! PHASE TWO RULES !!! * PHASE TWO RULES !!! PHASE TWO RULES !!!
	 * PHASE TWO RULES !!! * PHASE TWO RULES !!! PHASE TWO RULES !!! PHASE TWO
	 * RULES !!! *
	 ****************************************************************/

	final int BEGIN = 144;
	final int END = 145;
	final int POUND = 146;
	final int MAXFREQSTRING = 147;
	final int ID = 148;
	final int EQUAL = 149;
	final int SEMICOLON = 150;
	final int REPLACE = 151;
	final int REGEX = 152;
	final int WITH = 153;
	final int ASCIISTR = 154;
	final int WORD_IN = 155;
	final int RECURSIVEREPLACE = 156;
	final int PRINT = 157;
	final int GREATEREXCLAM = 158;
	final int COMMA = 159;
	final int FIND = 160;
	final int DIFF = 161;
	final int UNION = 162;
	final int INTERS = 163;
	final int LEFT_PAREN = 164;
	final int RIGHT_PAREN = 165;

	// <MiniRE-program> --> begin <statement-list> end
	public void MiniREprogram() {
		Node begin;
		Node statementList = new Node("<statement-list>", "statementList", head, null);
		Node end;
		token = peekToken();
		if (token.getType() == BEGIN) {
			matchToken();
			begin = new Node("MiniRE-program", "begin", head, null);
			head.addChild(begin);
			head.addChild(statementList);
			statementList(statementList);
			if ((token = peekToken()).getType() == END) {
				matchToken();
				end = new Node("MiniRE-program", "end", head, null);
				head.addChild(end);
			} else {
				System.err.println("MiniRE-Program missing 'end'");
			}
		} else {
			System.err.println("MiniRE-Program missing 'begin' found.");
		}
	}

	// <statement-list> --> <statement><statement-list-tail>
	public void statementList(Node node) {
		statement(node);
		statementListTail(node);
	}

	// <statement-list-tail> --> <statement><statement-list-tail> | [empty
	// string]
	public Node statementListTail(Node node) {
		if (statement(node) == null) {
			return null;
		} else {
			return statementListTail(node);
		}
	}

	// <statement> --> ID = <exp> ;
	// <statement> --> ID = # <exp> ;
	// <statement> --> ID = maxfreqstring (ID);
	// <statement> --> replace REGEX with ASCII-STR in <file-names> ;
	// <statement> --> recursivereplace REGEX with ASCII-STR in <file-names> ;
	// <statement> --> print ( <exp-list> ) ;
	public Node statement(Node node) {
		token = peekToken();
		if (token.getType() == ID) {
			matchToken();
			Node id = new Node("<statement>", token.getId(), null, null);
			if ((token = peekToken()).getType() == EQUAL) {
				matchToken();
				Node equal = new Node("<statement>", "=", node, null);
				node.addChild(equal);
				id.setParent(equal);
				equal.addChild(id);
				if ((token = peekToken()).getType() == POUND) {
					matchToken();
					Node pound = new Node("<statement>", "#", equal, null);
					equal.addChild(pound);
					exp(pound);
					if ((token = peekToken()).getType() == SEMICOLON) {
						matchToken();
						return equal;
					} else {
						System.err.println("Statement missing ';'");
					}
				} else if (token.getType() == MAXFREQSTRING) {
					matchToken();
					Node maxfreqstring = new Node("<statement>", "maxfreqstring", equal, null);
					equal.addChild(maxfreqstring);
					if ((token = peekToken()).getType() == LEFT_PAREN) {
						matchToken();
						if ((token = peekToken()).getType() == ID) {
							matchToken();
							Node id2 = new Node("<statement>", token.getId(), maxfreqstring, null);
							maxfreqstring.addChild(id2);
							if ((token = peekToken()).getType() == RIGHT_PAREN) {
								matchToken();
								if ((token = peekToken()).getType() == SEMICOLON) {
									matchToken();
									return equal;
								} else {
									System.err.println("Statement missing ';'");
								}
							} else {
								System.err.println("maxfreqstring missing ')'");
							}
						}
					} else {
						System.err.println("maxfreqstring missing the '('");
					}
				} else {
					exp(equal);
					if ((token = peekToken()).getType() == SEMICOLON) {
						matchToken();
						return equal;
					} else {
						System.err.println("Statement missing ';'");
					}
				}
			} else {
				System.err.println("statement missing '='");
			}
		} else if (token.getType() == REPLACE) {
			matchToken();
			Node replace = new Node("<statement>", "replace", node, null);
			node.addChild(replace);
			if ((token = peekToken()).getType() == REGEX) {
				matchToken();
				Node regex = new Node("<statement>", token.getRegex(), null, null);
				if ((token = peekToken()).getType() == WITH) {
					matchToken();
					Node with = new Node("<statement>", "with", replace, null);
					replace.addChild(with);
					regex.setParent(with);
					with.addChild(regex);
					if ((token = peekToken()).getType() == ASCIISTR) {
						matchToken();
						Node asciistr = new Node("<statement>", token.getAsciiString(), with, null);
						with.addChild(asciistr);
						if ((token = peekToken()).getType() == WORD_IN) {
							matchToken();
							fileNames(replace);
							if ((token = peekToken()).getType() == SEMICOLON) {
								matchToken();
								return replace;
							} else
								System.err.println("Statement missing ';'");
						} else {
							System.err.println("Replace missing 'in'");
						}
					} else {
						System.err.println("Replace missing ASCII-STR");
					}
				} else {
					System.err.println("Replace missing 'with'");
				}
			} else {
				System.err.println("Replace missing REGEX");
			}
		} else if (token.getType() == RECURSIVEREPLACE) {
			matchToken();
			Node recursivereplace = new Node("<statement>", "recursivereplace", node, null);
			node.addChild(recursivereplace);
			if ((token = peekToken()).getType() == REGEX) {
				matchToken();
				Node regex = new Node("<statement>", token.getRegex(), null, null);
				if ((token = peekToken()).getType() == WITH) {
					matchToken();
					Node with = new Node("<statement>", "with", recursivereplace, null);
					recursivereplace.addChild(with);
					regex.setParent(with);
					with.addChild(regex);
					if ((token = peekToken()).getType() == ASCIISTR) {
						matchToken();
						Node asciistr = new Node("<statement>", token.getAsciiString(), with, null);
						with.addChild(asciistr);
						if ((token = peekToken()).getType() == WORD_IN) {
							matchToken();
							fileNames(recursivereplace);
							if ((token = peekToken()).getType() == SEMICOLON) {
								matchToken();
								return recursivereplace;
							} else
								System.err.println("Statement missing ';'");
						} else {
							System.err.println("Replace missing 'in'");
						}
					} else {
						System.err.println("Replace missing ASCII-STR");
					}
				} else {
					System.err.println("Replace missing 'with'");
				}
			} else {
				System.err.println("Replace missing REGEX");
			}
		} else if (token.getType() == PRINT) {
			matchToken();
			Node print = new Node("<statement>", "print", node, null);
			node.addChild(print);
			if ((token = peekToken()).getType() == LEFT_PAREN) {
				matchToken();
				expList(print);
				if ((token = peekToken()).getType() == RIGHT_PAREN) {
					matchToken();
					if ((token = peekToken()).getType() == SEMICOLON) {
						matchToken();
						return print;
					}
				}
				System.err.println("Print is missing ')'");
			} else {
				System.err.println("Print is missing '('");
			}
		}
		return null;
	}

	// <file-names> --> <source-file> >! <destination-file>
	public void fileNames(Node node) {
		Node greaterexclam = new Node("<file-names>", ">!", node, null);
		sourceFile(greaterexclam);
		if ((token = peekToken()).getType() == GREATEREXCLAM) {
			matchToken();
			node.addChild(greaterexclam);
			destinationFile(greaterexclam);
		}
	}

	// <source-file> --> ASCII-STR
	public void sourceFile(Node node) {
		if ((token = peekToken()).getType() == ASCIISTR) {
			matchToken();
			Node sourcefile = new Node("<soure-file>", token.getAsciiString(), node, null);
			node.addChild(sourcefile);
			return;
		} else
			System.err.println("Source file missing");
	}

	// <destination-file> --> ASCII-STR
	public void destinationFile(Node node) {
		if ((token = peekToken()).getType() == ASCIISTR) {
			matchToken();
			Node destinationfile = new Node("<destination-file>", token.getAsciiString(), node, null);
			node.addChild(destinationfile);
			return;
		} else
			System.err.println("Destination file missing");
	}

	// <exp-list> --> <exp> <exp-list-tail>
	public void expList(Node node) {
		exp(node);
		expListTail(node);
	}

	// <exp-list-tail> --> , <exp> <exp-list-tail>
	public void expListTail(Node node) {
		if ((token = peekToken()).getType() == COMMA) {
			matchToken();
			exp(node);
			expListTail(node);
		}
	}

	// <exp> --> ID | ( <exp> )
	// <exp> --> <term> <exp-tail>
	public void exp(Node node) {
		if ((token = peekToken()).getType() == ID) {
			matchToken();
			Node id = new Node("<exp>", token.getId(), node, null);
			node.addChild(id);
			return;
		} else if (token.getType() == LEFT_PAREN) {

			matchToken();
			exp(node);
			if ((token = peekToken()).getType() == RIGHT_PAREN) {
				matchToken();
				return;
			} else
				System.err.println("expression is missing ')'");

		} else {
			Node term;
			Node tail;
			term = term();
			tail = expTail(term, node);
			if (tail == null) {
				node.addChild(term);
				term.setParent(node);
			}
		}
	}

	// <exp-tail> --> <bin-op> <term> <exp-tail>
	// <exp-tail> --> [empty string]
	public Node expTail(Node term, Node node) {
		token = peekToken();
		Node binOp = binOp(node);
		if (binOp == null) {
			return null;
		} else {
			binOp.addChild(term);
			term.setParent(binOp);
			Node term2 = term();
			Node tail = expTail(term2, binOp);
			if (tail == null) {
				binOp.addChild(term2);
				term2.setParent(binOp);
			}
			return binOp;
		}
	}

	// <term > --> find REGEX in <file-name>
	public Node term() {
		if ((token = peekToken()).getType() == FIND) {
			matchToken();
			Node find = new Node("<term>", "find", null, null);
			if ((token = peekToken()).getType() == REGEX) {
				matchToken();
				Node regex = new Node("<term>", token.getRegex(), find, null);
				find.addChild(regex);
				if ((token = peekToken()).getType() == WORD_IN) {
					matchToken();
					fileName(find);
					return find;
				} else {
					System.err.println("term is missing 'in'");
					return null;
				}
			} else {
				System.err.println("term is missing REGEX");
				return null;
			}
		} else {
			System.err.println("term is missing 'find'");
			return null;
		}
	}

	// <file-name> --> ASCII-STR
	public void fileName(Node node) {
		if ((token = peekToken()).getType() == ASCIISTR) {
			matchToken();
			Node asciistr = new Node("<file-name>", token.getAsciiString(), node, null);
			node.addChild(asciistr);
		}
	}

	// <bin-op> --> diff | union | inters
	public Node binOp(Node node) {
		Node binOp = null;
		token = peekToken();
		if (token.getType() == DIFF) {
			matchToken();
			binOp = new Node("<bin-op>", "diff", node, null);
		} else if (token.getType() == UNION) {
			matchToken();
			binOp = new Node("<bin-op>", "union", node, null);
		} else if (token.getType() == INTERS) {
			matchToken();
			binOp = new Node("<bin-op>", "inters", node, null);
		} else {
			return null;
		}
		node.addChild(binOp);
		return binOp;

	}

	/****************************************************************
	 * PHASE ONE RULES !!! PHASE ONE RULES !!! PHASE ONE RULES !!! * PHASE ONE
	 * RULES !!! PHASE ONE RULES !!! PHASE ONE RULES !!! * PHASE ONE RULES !!!
	 * PHASE ONE RULES !!! PHASE ONE RULES !!! * PHASE ONE RULES !!! PHASE ONE
	 * RULES !!! PHASE ONE RULES !!! * PHASE ONE RULES !!! PHASE ONE RULES !!!
	 * PHASE ONE RULES !!! * PHASE ONE RULES !!! PHASE ONE RULES !!! PHASE ONE
	 * RULES !!! *
	 ****************************************************************/

	public Token peekToken() {
		return list.get(listPos);
	}

	public void matchToken() {
		listPos++;
	}

	void regExMain(String line) {
		lexSpec = line;
		includeFlag = false;
		excludeFlag = false;
		excludeSet = false;
		regExp();
	}

	void regExp() {
		regExpOne();
		regExpTail();
	}

	void regExpTail() {
		token = peekToken();
		if (token.getType() == -1) {
			return; // done with this line
		}
		if (token.getType() == '|') {
			regExpOne();
			regExpTail();
		} else {
			return; // empty string
		}
	}

	void regExpOne() {
		regExpTwo();
		regExpOneTail();
	}

	void regExpOneTail() {
		token = peekToken();
		if (token.getType() == -1) {
			return; // done with this line
		}
		if (token.getType() == '(' || isReChar(token.getType())
				|| token.getType() == '.' || token.getType() == '['
				|| token.getType() >= 144) {
			regExpTwo();
			regExpOneTail();
		} else {
			return; // empty string
		}
	}

	void regExpTwo() {
		token = peekToken();
		if (token.getType() == -1) {
			return; // done with this line
		}
		if (token.getType() == '(') {
			regExp();
			token = peekToken();
			if (token.getType() == ')') {
			} else {
				regExpFail();
			}
			regExpTwoTail();
		} else if (isReChar(token.getType())) {
			reChar();
			regExpTwoTail();
		} else {
			regExpThree();
		}
	}

	void regExpTwoTail() {
		token = peekToken();
		if (token.getType() == '*' || token.getType() == '+') {
		} else {
			return; // empty string
		}
	}

	void regExpThree() {
		token = peekToken();
		if (token.getType() == '.' || token.getType() == '['
				|| token.getType() >= 144) {
			charClass();
		} else {
			return; // empty string
		}
	}

	void charClass() {
		token = peekToken();
		if (token.getType() == -1) {
			return; // done with this line
		}
		if (token.getType() == '.') {
		} else if (token.getType() == '[') {
			charClassOne();
		} else {
			definedClass();
		}
	}

	void charClassOne() {
		token = peekToken();
		if (token.getType() == -1) {
			return; // done with this line
		}
		if (token.getType() == '^') {
			excludeSet();
		} else {
			charSetList();
		}
	}

	void charSetList() {
		token = peekToken();
		if (token.getType() == -1) {
			return; // done with this line
		}
		if (isClsChar(token.getType())) {
			charSet();
			charSetList();
		} else if (token.getType() == ']') {
		}
	}

	void charSet() {
		token = peekToken();
		if (token.getType() == -1) {
			return; // done with this line
		}
		if (isClsChar(token.getType())) {
			clsChar();
			charSetTail();
		}
	}

	void charSetTail() {
		if (peekToken().getType() == '-') {
			pos++;
			clsChar();
		} else {
			return; // empty string
		}
	}

	void excludeSet() {
		token = peekToken();
		if (token.getType() == -1) {
			return; // done with this line
		}
		if (token.getType() == '^') {
			charSet();
			if (peekToken().getType() == ']') {
				pos++;
				insideBracket = false;
				if (peekToken().getType() == 'I') {
					pos++;
					if (peekToken().getType() == 'N') {
						pos++;
						excludeSetTail();
					}
				}
			} else {
				regExpFail();
			}
		} else {
			regExpFail();
		}
	}

	void excludeSetTail() {
		if (peekToken().getType() == '[') {
			pos++;
			insideBracket = true;
			if (isClsChar(peekToken().getType())) {
				charSet();
			}
			if (peekToken().getType() == ']') {
				pos++;
				insideBracket = false;
			}
		} else {
			definedClass();
		}
	}

	void definedClass() {
		token = peekToken();
		if (idFlag) {
		} else {
			for (CharClass c : characterClasses) {
				if (c.getValue() == token.getType()) {

					includeValues.clear();
					includeValues.addAll(c.getValidChars());
					includeValues.removeAll(excludeValues);

					newestCharClass.setValidChars(includeValues);
					pos += c.getName().length();
					break;
				}
			}
		}
	}

	void reChar() {
		token = peekToken();
		if (isReChar(token.getType())) {
			reFlag = true;
		} else {
			regExpFail();
		}
	}

	boolean isReChar(int check) {

		if (check >= 32 && check <= 142 && check != ' ' && check != '\\'
				&& check != '*' && check != '+' && check != '?' && check != '|'
				&& check != '[' && check != ']' && check != '(' && check != ')'
				&& check != '.' && check != '\'' && check != '\"'
				&& check != IN && check != ESCAPE_UP_ARROW
				&& check != ESCAPE_MINUS && check < 144) {

			return true;
		}

		else {
			return false;
		}

	}

	void clsChar() {
		token = peekToken();
		if (isClsChar(token.getType())) {
			clsFlag = true;
		} else {
			regExpFail();
		}
	}

	boolean isClsChar(int check) {
		if (check >= 32 && check <= 142 && check != '\\' && check != '^'
				&& check != '-' && check != '[' && check != ']'
				&& check != ESCAPE_SPACE && check != ESCAPE_ASTERISK
				&& check != ESCAPE_PLUS && check != ESCAPE_QUESTION
				&& check != ESCAPE_OR && check != ESCAPE_LEFT_PAREN
				&& check != ESCAPE_RIGHT_PAREN && check != ESCAPE_PERIOD
				&& check != ESCAPE_SINGLE_QUOTE && check != ESCAPE_DOUBLE_QUOTE) {
			return true;
		} else {
			return false;
		}
	}

	void regExpFail() {
		System.out.println("Regex syntax is incorrect.");
	}

	boolean isValid() {
		return validRegex;
	}

	void createTable() {
		System.out.println("Done.");
	}

	CharClass createCharClass(String line) {
		String newCharName = "";
		while (line.charAt(pos) != ' ') {
			newCharName += line.charAt(pos);
			pos++;
		}
		while (line.charAt(pos) == ' ') {
			pos++;
		}
		CharClass newestChar = new CharClass(newCharName, nextAsciiValue);
		nextAsciiValue++;
		return newestChar;
	}

	IdClass createIdClass(String line) {
		String newIdName = "";
		while (line.charAt(pos) != ' ') {
			newIdName += line.charAt(pos);
			pos++;
		}
		while (line.charAt(pos) == ' ') {
			pos++;
		}
		// Start of a small NFA
		lastState++;
		currState = lastState;
		startState = lastState;
		endState = 0;
		newestId = new IdClass(newIdName, lastState);

		// Connect to other NFAs
		set.add(startState);
		return newestId;
	}
}
